Target Sum

Statement#

Given an array of positive integers arr and a target T, build an expression using these numbers by inserting a $+$ or a $-$ before each integer, and evaluating this expression. Find the total number of different expressions that evaluate to T.

For example, consider an array [1, 1] and a target 0, we can build the following expressions:

The total number of expressions that evaluate to the target are 2.

Constraints:

• $1 \leq$ arr.length $\leq 40$

• $0 \leq$ arr[i] $\leq 1000$

• $0 \leq$ sum(arr[i]) $\leq 1000$

• $-1000 \leq$ T $\leq 1000$

Examples#

Try it yourself#

Implement your solution in the following playground.

Note: If you clicked the "Submit" button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution#

We will first explore the naive recursive solution to this problem and then see how it can be improved using the 0/1 Knapsack dynamic programming pattern.

Naive approach#

A naive approach to this problem is to find all expressions using the given numbers and then count the number of expressions that evaluate to the given target.

For example, we have an array [2, 1, 2], and we can build the following expressions:

Now, for a given target, we can count the number of expressions that evaluate to that target. For example, if the target is –1, we can count that 2 expressions evaluate to –1.

The calculation above shows that we need a recursive solution to make all possible expressions. In other words, we divide the problem into subproblems, and for each number, we place a $+$ or $-$ before it and generate new expressions.

Let’s implement the algorithm as discussed above:

Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.

Time complexity#

The time complexity of the naive approach is $O(2^n)$, where $n$ is the total number of integers. This is because we have two possible choices every time, either to assign a $+$ or a $-$ sign to the array elements.

Space complexity#

As the maximum depth of the recursive call tree is $n$, and each call stores its data on the stack, the space complexity of this approach is $O(n)$.

Optimized solution using dynamic programming#

Now, let us improve the recursive solution using top-down and bottom-up approaches.

Top-down solution#

The top-down solution, commonly known as the memoization technique, is an enhancement of the recursive solution. It overcomes the problem of calculating redundant solutions over and over again by storing them in an array.

In the recursive solution, when we generate two new expressions by inserting a $+$ or a $-$ before a number, all the array elements before the current element are computed. However, we had already evaluated them in the previous recursive calls. For example, consider an array [1, 2, 1]. Suppose we have already processed the first two elements. For the last element, two new expressions can be generated by placing a $+$ or a $-$ before it. While evaluating these expressions, the first two elements will be processed again, although we have already computed them in previous iterations. This becomes obvious when we list down all the possible expressions:

This results in many redundant recursive calls. To avoid this, we create a lookup table called dp of $n$ rows and $2*sum(arr)+1$ columns. The number of rows represents the number of given integers and the number of columns represents all possible target sums that can be built using these integers. For any given integer, whenever we generate and evaluate an expression, we store it at dp[i][T], where i and T represent the index of the integer and the generated sum, respectively. At any later time, if we encounter the same expression, we can return the stored result from the table with an $O(1)$ lookup time instead of recalculating that expression.

Let’s implement the algorithm as discussed above:

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

As we avoided redundant calculations by storing all the intermediate results in a lookup table, the time complexity of this approach is reduced to $O(n \times k)$, where $n$ is the size of the array and $k=sum(arr)$.

Space complexity#

The space taken by the lookup table is $O(n \times k)$, where $n$ is the size of the array and $k=sum(arr)$.

Bottom-up solution#

The bottom-up solution, also known as the tabulation technique, is an iterative method of solving dynamic programming problems. Here, we will again create a lookup table of size $n \times 2*sum(arr)+1$. The table is initialized with 0 except for the indexes corresponding to the first integer. Two expressions can be generated using the first integer by inserting a $+$ or a $-$ before it. Therefore, we store 1 at the respective indices.

As we see in the code below, the algorithm iterates over all integers and for every possible target sum t, it checks if it was generated during the previous iterations i.e., if dp[i-1][total+t] > 0, where total is the sum of all elements of the array. If it was generated, two new expressions are considered by inserting a $+$ or a $-$ before the current integer and the count of expressions is increased i.e., dp[i-1][total+t] is added to the values of dp[i][total+t+arr[i]] and dp[i][total+t-arr[i]].

Let’s look at the following illustration to get a better understanding of the solution: